package com.localking.algorithm.leetcode.array.matrix

/**
 * Given a non-negative index k where k <= 33, return the k(th) index row of the Pascal's triangle.
 * Note that the row index starts from 0.
 *
 * Example:
 * Input: 3
 * Output: [1, 3, 3, 1]
 *
 * Follow up:
 * Could you optimize you algorithm to use only O(k) extra space?
 *
 * @author jinbo
 */
object PascalTriangle2 {
  def main(args: Array[String]): Unit = {
    print(getRow3(4))
  }

  def getRow(rowIndex: Int): List[Int] = {
    rowIndex match {
      case 0 => List(1)
      case 1 => List(1, 1)
      case _ =>
        val previewRow: List[Int] = getRow(rowIndex - 1)
        var currentRow: List[Int] = List(1)
        for (i <- 1 until rowIndex) {
          currentRow :+= (previewRow(i - 1) + previewRow(i))
        }
        currentRow :+ 1
    }
  }

  /**
   * 组合公式 C(n, i) = n! / i! * (n-i)!
   * 第 i + 1 项的值为 （(n - i) / i + 1） * 第 i 项
   *
   * @param rowIndex rowIndex
   *
   * @return List[Int]
   */
  def getRow2(rowIndex: Int): List[Int] = {
    val array: Array[Int] = Array.fill(rowIndex + 1)(1)
    for (i <- 1 until rowIndex) {
      val value = array(i - 1).toLong * (rowIndex + 1 - i) / i
      array(i) = value.toInt
    }
    array.toList
  }

  def getRow3(rowIndex: Int): List[Int] = {
    val array = Array.fill(rowIndex + 1)(1)
    for (
      i <- 0 to rowIndex;
      j <- i - 1 until 0 by -1
    ) {
      array(j) += array(j - 1)
    }
    array.toList
  }
}
